Skip graph

Skip graphs are a kind of distributed data structure based on skip lists. They have the full functionality of a balanced tree in a distributed system. Skip graphs are mostly used in searching peer-to-peer networks. As they provide the ability to query by key ordering, they improve other search tools based on the hash table functionality only. In contrast to skip lists and other tree data structures, they are very resilient and can tolerate a large fraction of node fails. Also, constructing, inserting, searching and repairing a skip graph that was disturbed by failing nodes can be done by simple and straightforward algorithms.[1]

References

  1. ^ James Aspnes; Gauri Shah. "Skip Graphs". http://www.cs.yale.edu/: Computer Science – Yale University. http://www.cs.yale.edu/homes/aspnes/papers/skip-graphs-journal.pdf. "Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, simple and straightforward algorithms can be used to construct a skip graph, insert new nodes into it, search it, and detect and repair errors in a skip graph introduced due to node failures."